package com.wuxuan.algorithm_homework.stackAndQueue;

import java.util.Stack;

/**
 * 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(offer、peek、poll、isEmpty)
 * 实现 MyQueue 类:
 * void push(int x)将元素x推到队列的未尾
 * int pop()从队列的开头移除并返回元素
 * int peek()返回队列开头的元素
 * boolean isEmpty()如果队列为空，返回true:否则，返回false
 */
public class MyQueue {
    // | 1 2 3
    // |

    // | 4
    // | 3 2 1

    //storage:储存
    //retrieval:检索
    private final Stack<Integer> strorageStack;
    private final Stack<Integer> retrievalStack;

    //初始化
    public MyQueue() {
        strorageStack = new Stack<>();
        retrievalStack = new Stack<>();
    }

    public void push(int value) {
        strorageStack.push(value);
    }

    //平均时间复杂度：O(n) / n = O(1)
    public Integer pop() {
        if (retrievalStack.isEmpty()) {
            loadMore();
        }

        if (retrievalStack.isEmpty()) {
            return null;
        }

        return retrievalStack.pop();
    }

    public Integer peek() {
        if (retrievalStack.isEmpty()) {
            loadMore();
        }

        if (retrievalStack.isEmpty()) {
            return null;
        }

        return retrievalStack.peek();
    }

    public boolean isEmpty() {
//        if (strorageStack.isEmpty() && retrievalStack.isEmpty()) {
//            return true;
//        }
//        return false;
        //简化如下：
        return strorageStack.isEmpty() && retrievalStack.isEmpty();
    }

    private void loadMore() {
        while (!strorageStack.isEmpty()) {
            retrievalStack.push(strorageStack.pop());
        }
    }
}
